// cf-r295-div2(520)-d
// 题意：给你一个二维坐标系，x轴代表地面，y轴代表高度，
//       现已知n(<=100000)个单位方块的位置，整个局面稳定仅当所有方块稳定。
//       一个方块(x, y)稳定当前仅当它在地面(y=0)或者(x-1, y-1),
//       (x, y), (x+1, y)这三个位置任意一个有方块。保证初始局面稳定。
//       每个方块按读入顺序标号[0, n-1]。
//       然后现在有两个人，按顺序取走方块，取走的方块按取走的顺序从
//       左往右排成一排构成一个n进制数。
//       第一个人先取，第二个人后取，第一个人总是希望最后数字尽量大，
//       第二个人总是希望最后的数字尽量小，每次取走后依旧要保持局面稳定。
//       问最后的数字是多少。
//
// 题解：看着这题这么复杂，其实是水题，就是代码量有点大。
//       首先贪心分析下最后的数字肯定是确定的，然后只需要用两个优先队列
//       维护一下就行。优先队列维护条件稍微有那么点多（其实也不多）。
//
// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

//#define __DEBUG

struct cube { int x, y, id; };

bool operator<(cube const & a, cube const & b)
{
	return a.y < b.y || (a.y == b.y && a.x < b.x);
}

std::istream & operator>>(std::istream & is, cube & a)
{
	is >> a.x >> a.y;
	return is;
}

std::vector<cube> da;
std::vector<int> ans;

int const maxn = 100007;
bool removed[maxn];
int n;

using graph_type = std::vector<std::vector<int>>;
graph_type rely_on;
graph_type support;

void add_edge(int x, int y, graph_type & g)
{
	g[x].push_back(y);
}

int find_exist(cube const & tmp)
{
	auto t1 = std::lower_bound(da.begin(), da.end(), tmp);
	auto t2 = std::upper_bound(da.begin(), da.end(), tmp);
	if (t1 == t2 - 1) return t1 - da.begin();
	return -1;
}

void try_add(int x, cube const & tmp, graph_type & g)
{
	int t = find_exist(tmp);
	if (t == -1) return;
	add_edge(x, t, g);
}

void build_graph()
{
	for (int i = 0; i < n; i++) {
		cube & t = da[i];
		// rely_on
		if (t.y) {
			cube tmp = t; tmp.y--; tmp.x--;
			try_add(i, tmp, rely_on);
			tmp.x = t.x;
			try_add(i, tmp, rely_on);
			tmp.x = t.x + 1;
			try_add(i, tmp, rely_on);
		}

		// support
		cube tmp = t; tmp.y++; tmp.x--;
		try_add(i, tmp, support);
		tmp.x = t.x;
		try_add(i, tmp, support);
		tmp.x = t.x + 1;
		try_add(i, tmp, support);
	}
}

bool removable(int x)
{
	if (!support[x].size()) return true;
	for (auto i : support[x]) {
		if (removed[i]) continue;
		int t = rely_on[i].size();
		for (auto j : rely_on[i])
			if (removed[j]) t--;
		if (t == 1) return false;
	}
	return true;
}

auto cmp = [](int a, int b) { return da[a].id > da[b].id; };
std::priority_queue<int, std::vector<int>, decltype(cmp)> small(cmp);

auto cmp2 = [](int a, int b) { return da[a].id < da[b].id; };
std::priority_queue<int, std::vector<int>, decltype(cmp2)> big(cmp2);

void check(int now)
{
	cube tmp = da[now];
	tmp.y--; tmp.x--;
	int t = find_exist(tmp);
	if (t != -1 && !removed[t] && removable(t)) {
		big.push(t);
		small.push(t);
	}
	tmp.x = da[now].x;
	t = find_exist(tmp);
	if (t != -1 && !removed[t] && removable(t)) {
		big.push(t);
		small.push(t);
	}
	tmp.x = da[now].x + 1;
	t = find_exist(tmp);
	if (t != -1 && !removed[t] && removable(t)) {
		big.push(t);
		small.push(t);
	}
	tmp.x = da[now].x + 1; tmp.y = da[now].y;
	t = find_exist(tmp);
	if (t != -1 && !removed[t] && removable(t)) {
		big.push(t);
		small.push(t);
	}
	tmp.x = da[now].x - 1; tmp.y = da[now].y;
	t = find_exist(tmp);
	if (t != -1 && !removed[t] && removable(t)) {
		big.push(t);
		small.push(t);
	}
}

int const mo = 1000000009;

long long calc()
{
	long long ret = 0, pm = 1;
	for (int i = n - 1; i >= 0; i--, pm = (pm * n) % mo)
		ret = (ret + (ans[i] * pm) % mo) % mo;
	return ret;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin >> n;
	da.resize(n);
	support.resize(n);
	rely_on.resize(n);
	for (int i = 0; i < n; i++) {
		std::cin >> da[i];
		da[i].id = i;
	}
	std::sort(da.begin(), da.end());

	build_graph();

	for (int i = 0; i < n; i++)
		if (removable(i)) {
			small.push(i);
			big.push(i);
		}

	for (int i = 0; i < n; i++) {
		while (!big.empty() && (removed[big.top()] || !removable(big.top()))) big.pop();
		int now = big.top();
#ifdef __DEBUG
		std::cerr << "remove big: da[" << now << "] = {" << da[now].x << ", " << da[now].y << "}\n";
#endif
		ans.push_back(da[now].id);
		removed[now] = true;
		if (da[now].y) check(now);

		if (++i >= n) break;

		while (!small.empty() && (removed[small.top()] ||  !removable(small.top()))) small.pop();
		now = small.top();
#ifdef __DEBUG
		std::cerr << "remove small: da[" << now << "] = {" << da[now].x << ", " << da[now].y << "}\n";
#endif
		ans.push_back(da[now].id);
		removed[now] = true;
		if (da[now].y) check(now);
	}

	std::cout << calc() << '\n';
#ifdef __DEBUG
	std::cerr << "ans:\n";
	for (auto i : ans) std::cerr << i << ' ';
	std::cerr << '\n';
#endif
}

